package com.zhj.interview;

/**
 * 硬币问题
 * @author zhj
 */
public class Test07 {

    public static void main(String[] args) {
        int[] A = {2, 5, 7};
        System.out.println(funDP(A, 27));
    }

    public static int fun(int X) {
        if(X == 0) return 0;
        int res = Integer.MAX_VALUE - 1;
        if(X >= 2) {
            res = Math.min(fun(X-2), res);
        }
        if(X >= 5) {
            res = Math.min(fun(X-5), res);
        }
        if(X >= 7) {
            res = Math.min(fun(X-7), res);
        }
        return res + 1;
    }

    /**
     * 求解：最少多少枚硬币
     * 参数：A 是有多少元的硬币
     * 参数：M 是需要花多少钱
     */
    public static int funDP(int[] A, int M) {
        // 结果集
        int[] res = new int[M + 1];
        // 初始化
        res[0] = 0;
        // 计算
        for (int i = 1; i<= M; i++) {
            res[i] = Integer.MAX_VALUE;
            for (int j = 0; j < A.length; j++) {
                if (i >= A[j] && res[i - A[j]] != Integer.MAX_VALUE) {
                    res[i] = Math.min(res[i - A[j]] + 1, res[i]);
                }
            }
        }
        // 结果处理
        if (res[M] == Integer.MAX_VALUE) {
            res[M] = -1;
        }
        return res[M];
    }
}
